package lk;

import java.util.Arrays;

public class D230921 {
    // 找到最高海拔
    // 初始海拔为 0, 遍历数组, 更新最高的海拔
    // 时间: O(N)
    // 空间: O(1)
    public int largestAltitude(int[] gain) {
        int height = 0;
        int max = 0;
        for (int x : gain) {
            height += x;
            max = Math.max(max, height);
        }
        return max;
    }

    // 寻找数组的中心下标
    // 中心下标 左侧元素的和 等于 右侧元素的和
    // 时间: O(N)
    // 空间: O(1)
    public int pivotIndex(int[] nums) {
        // 1. 遍历数组, 求整个数组的和
        int rightSum = 0;
        for (int num : nums) {
            rightSum += num;
        }
        // 2. 再次遍历数组, 寻找中心下标
        int leftSum = 0;
        for (int i = 0; i < nums.length; i++) {
            rightSum -= nums[i];
            if (leftSum == rightSum) {
                return i;
            }
            leftSum += nums[i];
        }
        return -1;
    }
}
